difference between theory and practice: efficiency

In practice:

1. express F as a circuit CF

2. call on each player to secretly share $x_i$

3. proceed to perform " secret addition and multiplication" on secretly shared values

• cost: depth of $C_F$ times cost of secret multiplication

1 Introduction

Secrete Sharing:

Advantage of using polynomials

easy to combine two secrets multiplication by a publicly known constant

But when secrets are multiplied: it's hard

fan-in: [Electronics]the number of inputs that can be connected to the circuit.

Notions:

Our Solution:

dose evaluate the circuit level by level, but each level is simply a reconstruction of secrets

The Idea

completely randomize every input and output to each gate in $C_F$ plus a very simple error-correction procedure

error-correcting procedure

One-time tables

Analogous to one-time pad

One-time table: a set of precomputed values that support direct secure computation without broadcast or private channels

2 An Efficient Protocol for Circuit Evaluation

UnifSecret

UnifSecret:

generate uniformly random secrets by adding uniformly random secrets shared by each party.

Calculate Circuit:

Circuit：

• N wires carry inputs

• gates $g_k\in \{+,\times\}$: $x_k=g_k(x_{i_k},x_{j_k})$

• level($g_k$): depth of the gate

evaluate: 把电路的gates按照depth分层，一层一层的计算，每次计算出该层的输出（new secrets)，就是下一层的输入。

Share-Compute-Reveal Paradigm:

1. evaluate gates at each level

2. thereby produce new secrets $x_k$, until the final secret $x_N$is calculated

3. use REC reconstruct the result $x_N$

Additive Gate

An additive gate:

1. create N uniformly random values $r_i$ for every $x_i$ 用UnifySecret的方式，every party generate a random secret，其和就是分配给每个wire的random values。 （这里不考虑secret sharing，只考虑value calculation）

2. for every gate $g_k$ : compute $s_k=g_k(r_{i_k},r_{j_k})$ every party可以直接对random value (pieces)计算，这里是加法门，所以$s_k=r_{i_k}+r_{j_k}$。不过each party得到的其实是PIECE($s_k$)。

3. consider corrections $\Delta_i=r_i-x_i$ to each wire 对于一层gates而言，input wire的corrections (pieces)可以locally calculate。而当要计算output wire的corrections时，就需要REC input wire的correction，所有parties的pieces 加起来，得到$\Delta_i$。

4. compute the correction $\Delta_k$: output wire of $g_k(+)$
   1. praty know(pieces):
      1. random inputs $r_{i_k},r_{j_k}$and their results $s_k=r_{i_k}+r_{j_k}$
      2. random output $r_k$
      3. input wire corrections $\Delta_{i_k}, \Delta_{j_k}$
   2. party calculate output wire correction: $\Delta_k = r_k-s_k-\Delta_{i_k}-\Delta_{j_k}$
   3. $\Delta_k$ is a linear combination of "known" constant $\Delta_{i_k}$ and $\Delta_{j_k}$with the values $r_k$ and $s_k$ 刚刚也说过，在计算这一层gates前，需要reconstruct input wire的correction，所以计算时， $\Delta_{i_k}$ and $\Delta_{j_k}$是已经经过REC操作，every party都把他的pieces分享处理（但不会reveal info），得到 constant $\Delta_{i_k}$ and $\Delta_{j_k}$。

Multiplicative Gate:

Multiplicative gates:

• a linear combination: $\Delta_{k}=r_{k}-s_{k}-r_{i_{k}} \Delta_{j_{k}}-\Delta_{i_{k}} r_{i_{k}}-\Delta_{i_{k}} \Delta_{j_{k}}$

Security:

Cost of REC:

Figure 2: the whole protocol

2.1 An Optimization

Compress additive gates:

by computing the corrections to outputs at the same time as the corrections to input wires no "randomization" of additive gates

Example:

把先做乘法，在做什么加法两层运算，压缩为一层运算。

Add gate output correction和其input没有关系，包括$r_5,r_6,\Delta_5,\Delta_6$，反而是和前一层的MUL gates的input有关系。

Deduce：